package leetcode.weekly.week305;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

//Solution2Test
public class Solution2 {

	public int reachableNodes(int n, int[][] edges, int[] restricted) {
		Map<Integer, List<Integer>> map = new HashMap<>();
		int m = edges.length;
		for (int i = 0; i < m; i++) {
			int[] e = edges[i];
			int a = e[0], b = e[1];
			map.computeIfAbsent(a, key -> new ArrayList<>()).add(b);
			map.computeIfAbsent(b, key -> new ArrayList<>()).add(a);
		}
		Set<Integer> set = new HashSet<>();
		for (int r : restricted) {
			set.add(r);
		}
		Queue<Integer> queue = new LinkedList<>();
		int ans = 1;
		queue.add(0);
		boolean[] been = new boolean[n];
		been[0] = true;
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			List<Integer> nexts = map.get(cur);
			if (nexts == null) {
				continue;
			}
			for (int next : nexts) {
				if (!been[next] && !set.contains(next)) {
					been[next] = true;
					ans++;
					queue.add(next);
				}
			}
		}
		return ans;
	}

}
